/**
 * \file Graphe.hpp
 * \brief Le code des opérateurs du Graphe
 * \author Jean-Simon Garneau & Simon Falardeau
 * \version 0.1
 * \date Novembre 2011
 *
 * Implémentation de la classe générique Graphe
 */
#include "Graphe.h"
using namespace tp2;

/**
 * \fn Graphe<Objet>::Arc::Arc(Sommet* dest, int cout)
 * \brief Constructeur avec paramètres
 *
 * \param[in]	dest	L'adresse du sommet de destination
 * \param[in]	cout	Le cout de l'arc
 *
 * \post Un arc est créé avec les paramètres indiqués
 */

template<typename Objet>
Graphe<Objet>::Arc::Arc(Sommet* dest, int cout) :
		m_dest(dest), m_cout(cout), m_suivDest(0)
{
}

/**
 * \fn Graphe<Objet>::Arc::~Arc()
 * \brief Destructeur.
 *
 * \post Un arc est détruit
 */
template<typename Objet>
Graphe<Objet>::Arc::~Arc()
{
}

/**
 * \fn Graphe<Objet>::Sommet::Sommet(int numero, const Objet& etiquette)
 * \brief Constructeur avec paramètres.
 *
 * \param[in]	etiquette	Les donnees d'un sommet
 * \param[in]	numero	Le numéro du sommet
 * \post Le sommet est initialisé avec les paramètres indiqués
 */
template<typename Objet>
Graphe<Objet>::Sommet::Sommet(int numero, const Objet& etiquette) :
		m_numero(numero), m_etiquette(etiquette)
{
	m_listeDest = 0;

	m_etat = false;
	m_predecesseur = 0;
	m_cout = std::numeric_limits<int>::max();
	;

	m_precedent = 0;
	m_suivant = 0;
}

/**
 * \fn Graphe<Objet>::Sommet::Sommet(Sommet* source)
 * \brief Constructeur de copie.
 *
 * \param[in]	source	La source sommet à copier
 * \post	Une copie profonde du sommet a été effectuée à partir du sommet source
 */
template<typename Objet>
Graphe<Objet>::Sommet::Sommet(Sommet* source)
{
	m_numero = source->m_numero;
	m_etiquette = source->m_etiquette;

	m_etat = source->m_etat;
	m_cout = source->m_cout;

	m_predecesseur = source->m_predecesseur;

	m_listeDest = source->m_listeDest;

	m_precedent = source->m_precedent;
	m_suivant = source->m_suivant;
}

/**
 * \fn Graphe<Objet>::Sommet::~Sommet()
 * \brief Destructeur.
 * \post Le sommet est détruit
 */
template<typename Objet>
Graphe<Objet>::Sommet::~Sommet()
{
	while (m_listeDest != 0)
	{
		Arc* temp = m_listeDest;
		m_listeDest = temp->m_suivDest;
		delete temp;
	}
}

/**
 * \fn Graphe<Objet>::Graphe()
 * \brief Constructeur par défaut.
 * \post Un graphe vide est créé
 */
template<typename Objet>
Graphe<Objet>::Graphe()
{
	listSommets = 0;
	nbSommets = 0;
}

/**
 * \fn Graphe<Objet>::Graphe(const Graphe &source)
 * \brief Constructeur de copie.
 * \pre Il y a assez de mémoire pour copier le graphe 'source'
 * \exception	bad_alloc	Il n'y a pas assez de mémoire pour copier le graphe 'source'
 */
template<typename Objet>
Graphe<Objet>::Graphe(const Graphe &source)
{
	(*this) = source;
}

/**
 * \fn Graphe<Objet>::~Graphe()
 * \brief Destructeur.
 * \post La graphe est entièrement supprimé
 */
template<typename Objet>
Graphe<Objet>::~Graphe()
{
	while (listSommets != 0)
	{
		Sommet* temp = listSommets;
		listSommets = temp->m_suivant;
		delete temp;
	}
}

/**
 * \fn void Graphe<Objet>::ajouterSommet(int numero, const Objet& etiquette)
 * \brief Ajout d'un sommet au graphe.
 *
 * \param[in]	etiquette	Les donnees du sommet à ajouter
 * \param[in]	numero	Le numero du sommet à ajouter
 *
 * \pre	Il y a assez de mémoire pour ajouter un sommet
 * \pre	Il n'y a aucun sommet avec le même numéro dans le graphe
 *
 * \post	Un sommet contenant les informations passées en argument a été ajouté au Graphe
 *
 * \exception bad_alloc	Il n'y a pas assez de mémoire pour ajouter un sommet
 * \exceptionlogic_error	Il y a un sommet avec le même numéro dans le graphe
 *
 */
template<typename Objet>
void Graphe<Objet>::ajouterSommet(int numero, const Objet& etiquette)
{
	if (numero < 1)
		throw std::logic_error("Le numero doit être plus grand que 0");

	if (sommetExiste(numero) || etiquetteExiste(etiquette))
		throw std::logic_error("Un sommet du même numéro est déjà existant");

	Sommet* nouveau = new Sommet(numero, etiquette);

	if (estVide())
	{
		listSommets = nouveau;
	}
	else
	{
		Sommet* temp = listSommets;

		while (temp->m_suivant != 0)
		{
			temp = temp->m_suivant;
		}

		nouveau->m_precedent = temp;
		temp->m_suivant = nouveau;
	}

	nbSommets++;
}

/**
 * \fn void Graphe<Objet>::enleverSommet(int numero)
 * \brief Enlève un sommet du graphe ainsi que tous les arcs qui vont et partent de ce sommet.
 *
 * \param[in]	numero	Le numéro du sommet à enlever
 *
 * \pre	Il y a un sommet avec le numéro 'm_numero' dans le graphe
 * \post	Le sommet identifié par 'm_numero' a été enlevé du graphe
 *
 * \exceptino	logic_error	Il n'y a aucun sommet avec le numéro 'm_numero' dans le graphe
 *
 */
template<typename Objet>
void Graphe<Objet>::enleverSommet(int numero)
{
	if (!sommetExiste(numero))
		throw std::logic_error("Le sommet n'existe pas");

	Sommet* sommet = _getSommet(numero);

	for (Sommet* i = listSommets; i != 0; i = i->m_suivant)
	{
		if (arcExiste(i->m_numero, numero))
			enleverArc(i->m_numero, numero);
	}

	if (sommet->m_suivant == 0 && sommet->m_precedent == 0)
	{
		listSommets = 0;
	}
	else if (sommet->m_suivant == 0 && sommet->m_precedent != 0)
	{
		Sommet* precedent = sommet->m_precedent;
		precedent->m_suivant = 0;
	}
	else if (sommet->m_precedent == 0 && sommet->m_suivant != 0)
	{
		Sommet* suivant = sommet->m_suivant;
		listSommets = suivant;
		suivant->m_precedent = 0;
	}
	else
	{
		Sommet* suivant = sommet->m_suivant;
		Sommet* precedent = sommet->m_precedent;

		suivant->m_precedent = precedent;
		precedent->m_suivant = suivant;
	}

	delete sommet;
	nbSommets--;
}

/**
* \fn void Graphe<Objet>::ajouterArc(int numOrigine, int numDestination, int cout)
* \brief Ajout d'un arc au graphe.
*
* \param[in]	numOrigine	Le numéro du sommet d'origine
* \param[in]	numDestination	Le numéro du sommet de destination
* \param[in]	cout	Le cout de l'arc
*
* \pre 	Les deux sommets doivent exister
* \post	Un arc a été ajouté entre le sommet 'numeroOrigine' et le sommet 'numeroDestination'
*
* \exception	bad_alloc	Pas assez de mémoire pour alloué le nouvel arc
* \exception	logic_error	Un des deux sommets n'existe pas
* \exception	logic_error	Il y a déjà un arc orienté entre ces deux sommets
*/
template<typename Objet>
void Graphe<Objet>::ajouterArc(int numOrigine, int numDestination, int cout)
{
	if (arcExiste(numOrigine, numDestination))
		throw std::logic_error("L'arc existe déjà");

	if (!sommetExiste(numOrigine) || !sommetExiste(numDestination))
		throw std::logic_error("Un sommet est inexistant");

	Sommet* sommet = _getSommet(numOrigine);
	Arc* nouveau = new Arc(_getSommet(numDestination), cout);

	if (sommet->m_listeDest != 0)
	{
		Arc* temp = sommet->m_listeDest;

		while (temp->m_suivDest != 0)
		{
			temp = temp->m_suivDest;
		}

		temp->m_suivDest = nouveau;
	}
	else
	{
		sommet->m_listeDest = nouveau;
	}
}

/**
 *	\fn	void Graphe<Objet>::enleverArc(int numOrigine, int numDestination)
 *	\brief Enlève un arc du graphe.
 *
 *	\param[in]	numOrigine	Le numéro du sommet d'origine
 *	\param[in]	numDestination	Le numéro du sommet de destination
 *
 *	\pre	Les deux sommets identifiés par leur numéro doivent appartenir au graphe.
 *  \pre	Un arc reliant les deux sommets doit exister.
 *
 *  \post	Le graphe contient un arc en moins, le graphe inchangé sinon
 *
 *  \exception	logic_error	Un des deux sommets, ou les deux, n'existent pas
 *  \exception	logic_error	Il n'y a pas d'arc entre les 2 sommets
 */
template<typename Objet>
void Graphe<Objet>::enleverArc(int numOrigine, int numDestination)
{
	if (!arcExiste(numOrigine, numDestination))
		throw std::logic_error("L'arc n'existe pas");

	Sommet* sommet = _getSommet(numOrigine);
	Arc* arc = _getArc(_getSommet(numOrigine), _getSommet(numDestination));
	Arc* prec;

	if (arc == sommet->m_listeDest)
	{
		sommet->m_listeDest = arc->m_suivDest;
	}
	else
	{
		for (Arc* i = sommet->m_listeDest; i != 0; i = i->m_suivDest)
		{
			if (i != arc)
				prec = i;
			else
				break;
		}

		if (arc->m_suivDest == 0)
			prec->m_suivDest = 0;
		else
			prec->m_suivDest = arc->m_suivDest;
	}

	delete arc;
}

/**
 * \fn	int Graphe<Objet>::nombreSommets() const
 * \brief	Retourne le nombre de sommets dans la liste des sommets.
 * \post	Le graphe reste inchangé.
 * \return	Le nombre de sommets dans le graphe
 */
template<typename Objet>
int Graphe<Objet>::nombreSommets() const
{
	return nbSommets;
}

/**
 * \fn	bool Graphe<Objet>::estVide() const
 * \brief	Indique si la liste des sommets est vide.
 * \return	True si le graphe ne contient pas de sommets, false autrement
 * \post	Le graphe reste inchangé.
 */
template<typename Objet>
bool Graphe<Objet>::estVide() const
{
	return nbSommets == 0;
}

/**
 * \fn	std::vector<int> Graphe<Objet>::listerSommets() const
 * \brief	Retourne la liste des numéros des sommets dans un vecteur d'entiers.
 * \return	Un vector de type int qui contient une liste de tous les numéros des sommets
 * \post	Le graphe reste inchangé.
 */
template<typename Objet>
std::vector<int> Graphe<Objet>::listerSommets() const
{
	if (estVide())
		throw std::logic_error("Le graphe est vide");

	std::vector<int> v(nbSommets);
	Sommet* temp = listSommets;

	for (int i = 0; i < nbSommets; i++)
	{
		v[i] = temp->m_numero;
		if (temp->m_suivant != 0)
			temp = temp->m_suivant;
	}

	return v;
}

/**
 * \fn	std::vector<Objet> Graphe<Objet>::listerEtiquetteSommets() const
 * \brief	Retourne la liste des étiquettes des sommets dans un vecteur.
 * \return	Un vector de type Objet qui contient une liste de toutes les étiquettes des sommets
 * \post	Le graphe reste inchangé.
 */
template<typename Objet>
std::vector<Objet> Graphe<Objet>::listerEtiquetteSommets() const
{
	if (estVide())
		throw std::logic_error("Le graphe est vide");

	std::vector<Objet> v(nbSommets);
	Sommet* temp = listSommets;

	for (int i = 0; i < nbSommets; i++)
	{
		v[i] = temp->m_etiquette;
		if (temp->m_suivant != 0)
			temp = temp->m_suivant;
	}

	return v;
}

/**
 * \fn	int Graphe<Objet>::getNumeroSommet(const Objet& etiquette) const
 * \brief	Retourne le numéro d'un sommet selon son etiquette.
 *
 * \pre	Le sommet doit faire partie du graphe
 *
 * \param[in]	etiquette	L'étiquette d'un sommet
 *
 * \post	Le graphe reste inchangé.
 *
 * \exception	logic_error	Le sommet n'existe pas
 * \return	Le numéro du sommet recherché
 */
template<typename Objet>
int Graphe<Objet>::getNumeroSommet(const Objet& etiquette) const
{
	int num = 0;

	if (estVide())
		throw std::logic_error("Le graphe est vide");

	if (!etiquetteExiste(etiquette))
		throw std::logic_error("L'étiquette est inexistante dans le graphe");

	for (Sommet* i = listSommets; i != 0; i = i->m_suivant)
	{
		if (i->m_etiquette == etiquette)
		{
			num = i->m_numero;
			break;
		}
	}

	return num;
}

/**
 * \fn	bool Graphe<Objet>::sommetExiste(int numero) const
 * \brief	Retourne l'existence d'un sommet.
 *
 * \param[in]	numero	Le numéro du sommet
 *
 * \post	Le graphe reste inchangé.
 * \return	True si le sommet existe, false autrement
 *
 * \return	True si le sommet existe, false autrement
 */
template<typename Objet>
bool Graphe<Objet>::sommetExiste(int numero) const
{
	bool r = false;

	for (Sommet* i = listSommets; i != 0; i = i->m_suivant)
	{
		if (i->m_numero == numero)
		{
			r = true;
			break;
		}
	}

	return r;
}

/**
 * \fn	bool Graphe<Objet>::etiquetteExiste(Objet etiquette) const
 * \brief	Retourne si l'etiquette existe dans le graphe
 *
 * \param[in]	etiquette	L'etiquette qu'on veut rechercher
 *
 * \post Le graphe est inchangé
 * \return	True si l'etiquette existe, false autrement
 */
template<typename Objet>
bool Graphe<Objet>::etiquetteExiste(Objet etiquette) const
{
	bool r = false;

	for (Sommet* i = listSommets; i != 0; i = i->m_suivant)
	{
		if (i->m_etiquette == etiquette)
		{
			r = true;
			break;
		}
	}

	return r;
}

/**
 * \fn	Objet Graphe<Objet>::getEtiquetteSommet(int numero) const
 * \brief	Retourne l'étiquette d'un sommet.
 *
 * \pre	Le sommet doit exister
 *
 * \param[in]	numero	Le numéro du sommet
 *
 * \exception	logic_error	Il n'y a pas de sommets dans le graphe
 * \exception	logic_error	Le sommet n'existe pas
 *
 * \return	Le nom du sommet recherché
 */
template<typename Objet>
Objet Graphe<Objet>::getEtiquetteSommet(int numero) const
{
	Objet t;

	if (estVide())
		throw std::logic_error("Le graphe est vide");

	if (!sommetExiste(numero))
		throw std::logic_error("Le sommet est inexistant");

	for (Sommet* i = listSommets; i != 0; i = i->m_suivant)
	{
		if (i->m_numero == numero)
		{
			t = i->m_etiquette;
			break;
		}
	}

	return t;
}

/**
 * \fn	int Graphe<Objet>::ordreSortieSommet(int numero) const
 * \brief	Retourne l'ordre de sortie d'un sommet.
 *
 * \pre	Le sommet doit exister
 * \param[in]	numero	Le numéro du sommet
 * \exception	logic_error	Le sommet n'existe pas
 * \return	L'odre de sortie d'un sommet
 */
template<typename Objet>
int Graphe<Objet>::ordreSortieSommet(int numero) const
{
	int nb = 0;
	Arc* temp = _getSommet(numero)->m_listeDest;

	while (temp != 0)
	{
		nb++;
		temp = temp->m_suivDest;
	}

	return nb;
}

/**
 * \fn	int Graphe<Objet>::ordreEntreeSommet(int numero) const
 * \brief	Retourne l'ordre d'entrée d'un sommet.
 *
 * \pre	Le sommet doit exister
 *
 * \param[in]	numero	Le numéro du sommet
 * \return	L'odre d'entrée d'un sommet
 *
 * \exception	logic_error	Le sommet n'existe pas
 */
template<typename Objet>
int Graphe<Objet>::ordreEntreeSommet(int numero) const
{
	int nb = 0;
	Sommet* temp = listSommets;

	while (temp != 0)
	{
		if (arcExiste(temp->m_numero, numero))
			nb++;
		temp = temp->m_suivant;
	}

	return nb;
}

/**
 * \brief	Retourne la liste des numéros des sommets adjacents au sommet passé en argument dans un vecteur d'entiers.
 *
 * \pre	Le sommet doit appartenir au graphe
 *
 * \param[in]	numeroSommetsAdjacents	Le numéro du sommet dont on cherche les sommets adjacents
 * \post	Le graphe reste inchangé.
 *
 * \return	Un vector de type int qui contient une liste de tous les numéros des sommets adjacents au sommet demandé
 * \exception	logic_error	si le sommet n'existe pas
 */
template<typename Objet>
std::vector<int> Graphe<Objet>::listerSommetsAdjacents(
		int numeroSommetsAdjacents) const
{
	if (!sommetExiste(numeroSommetsAdjacents))
		throw std::logic_error("Le sommet est inexistant");

	std::vector<int> v;

	for (Arc* i = _getSommet(numeroSommetsAdjacents)->m_listeDest; i != 0;
			i = i->m_suivDest)
	{
		int t = i->m_dest->m_numero;
		v.push_back(t);
	}

	return v;
}

/**
 * \brief	Retourne l'existence d'un arc.
 * \pre	Les sommets doivent appartenir au graphe
 *
 * \param[in]	numOrigine	Le numéro du sommet d'origine
 * \param[in]	numDestination	Le numéro du sommet de destination
 *
 * \return	True si un arc existe entre les deux sommets, false autrement
 * \exception	logic_error	L'un ou l'autre, ou les 2 sommets ne font pas partie du graphe
 */
template<typename Objet>
bool Graphe<Objet>::arcExiste(int numOrigine, int numDestination) const
{
	bool flag = false;
	Sommet* temp = _getSommet(numOrigine);

	for (Arc* i = temp->m_listeDest; i != 0; i = i->m_suivDest)
	{
		Sommet* t = i->m_dest;
		if (t->m_numero == numDestination)
		{
			flag = true;
			break;
		}
	}

	return flag;
}

/**
 * \brief	Retourne le coût d'un arc passé en argument.
 * \pre	L'arc doit exister
 * \param[in]	numOrigine	Le numéro du sommet d'origine
 * \param[in]	numDestination	Le numéro du sommet de destination
 * \post Le graphe est inchangé
 * \return	Le coût de l'arc entre deux sommets
 */
template<typename Objet>
int Graphe<Objet>::getCoutArc(int numOrigine, int numDestination) const
{
	if (!arcExiste(numOrigine, numDestination))
		throw std::logic_error("l'arc est inexistamt");

	return _getArc(_getSommet(numOrigine), _getSommet(numDestination))->m_cout;
}

/**
 * \brief	Surcharge de l'opérateur d'affectation.
 * \pre	Il doit y avoir assez de mémoire.
 * \param[in]	source	Le graphe à copier
 * \post	Le graphe a un contenu identique à 'source'.
 * \exception	bad_alloc	S'il n'y a pas assez de mémoire.
 */
template<typename Objet>
const Graphe<Objet>& Graphe<Objet>::operator =(const Graphe& source)
{
	nbSommets = 0;
	listSommets = 0;

	for (Sommet* i = source.listSommets; i != 0; i = i->m_suivant)
	{
		ajouterSommet(i->m_numero, i->m_etiquette);
	}

	for (Sommet* i = source.listSommets; i != 0; i = i->m_suivant)
	{
		for (Arc* j = i->m_listeDest; j != 0; j = j->m_suivDest)
		{
			ajouterArc(i->m_numero, j->m_dest->m_numero, j->m_cout);
		}
	}

	return (*this);
}

/**
 * \brief	Trouve l'adresse d'un sommet à partir de son numéro.
 * \param[in]	numero	Le numéro du sommet
 * \post	L'adresse du sommet recherché est retournée
 */
template<typename Objet>
typename Graphe<Objet>::Sommet* Graphe<Objet>::_getSommet(int numero) const
{
	if (estVide())
		throw std::logic_error("Le graphe est vide");

	if (!sommetExiste(numero))
		throw std::logic_error("Le sommet est inexistant");

	Sommet* t = listSommets;

	while (t->m_numero != numero)
	{
		t = t->m_suivant;
	}

	return t;
}

/**
 * \brief	Trouve l'adresse d'un arc entre deux sommets.
 * \param[in]	origine	L'adresse du sommet d'origine
 * \param[in]	destination	L'adresse du sommet de destination
 * \return	L'adresse de l'arc trouvé entre le sommet d'origine et le sommet de destination
 */
template<typename Objet>
typename Graphe<Objet>::Arc* Graphe<Objet>::_getArc(Sommet* sommet1,
		Sommet* sommet2) const
{
	if (estVide())
		throw std::logic_error("Le graphe est vide");

	if (!arcExiste(sommet1->m_numero, sommet2->m_numero))
		throw std::logic_error("L'arc est inexistant");

	Arc* t = _getSommet(sommet1->m_numero)->m_listeDest;

	while (t->m_dest != sommet2)
	{
		t = t->m_suivDest;
	}

	return t;
}

/**
 * \brief	Déterminer la fermeture transitive du graphe.
 * \pre	Le graphe est correctement initialisé.
 * \post	La fermeture transitive du graphe est retournée.
 * \post	Le graphe original reste inchangé.
 * \exception	bad_alloc	si pas assez de mémoire application de l'algorithme de Floyd-Warshall
 */
template<typename Objet>
Graphe<Objet> Graphe<Objet>::fermetureGraphe() const
{
	Graphe<Objet> fermeture = *this;

	// Init infinite
	for (Sommet* i = fermeture.listSommets; i != 0; i = i->m_suivant)
	{
		for (Sommet* j = fermeture.listSommets; j != 0; j = j->m_suivant)
		{
			if (!fermeture.arcExiste(i->m_numero, j->m_numero))
			{
				if (i != j)
				{
					fermeture.ajouterArc(i->m_numero, j->m_numero,
							std::numeric_limits<int>::max());
				}
				else
				{
					fermeture.ajouterArc(i->m_numero, j->m_numero, 0);
				}
			}
		}
	}

	for (Sommet* k = fermeture.listSommets; k != 0; k = k->m_suivant)
	{
		for (Sommet* i = fermeture.listSommets; i != 0; i = i->m_suivant)
		{
			for (Sommet* j = fermeture.listSommets; j != 0; j = j->m_suivant)
			{
				Arc* c = fermeture._getArc(i, j);
				Arc* ik = fermeture._getArc(i, k);
				Arc* kj = fermeture._getArc(k, j);
				if (ik->m_cout != std::numeric_limits<int>::max()
						&& kj->m_cout != std::numeric_limits<int>::max())
					c->m_cout = std::min(c->m_cout, ik->m_cout + kj->m_cout);
			}
		}
	}

	return fermeture;
}

/**
 * \brief	Détermine si le graphe est fortement connexe ou non.
 * \post	true est retourné si le graphe est fortement connexe, false est retourné sinon
 * \return	true si le graphe est fortement connexe, false sinon
 */
template<typename Objet>
bool Graphe<Objet>::estFortementConnexe() const
{
	bool flag = true;
	Graphe<Objet> fermeture = fermetureGraphe();

	for (Sommet* i = fermeture.listSommets; i != 0; i = i->m_suivant)
	{
		for (Sommet* j = fermeture.listSommets; j != 0; j = j->m_suivant)
		{
			Arc* c = fermeture._getArc(i, j);
			if (c->m_cout == std::numeric_limits<int>::max())
			{
				flag = false;
				break;
			}
		}
	}

	return flag;
}

/**
 * \brief	Détermine les composantes fortement connexes et les mémorise dans un conteneur passé en paramètre.
 * \pre	Il y a assez de mémoire pour placer les composantes fortements connexes dans 'composantes'
 * \param[in]	composantes
 * \post	Les composantes fortement connexes du graphe sont placées dans 'composantes'
 * \exception	bad_alloc	Il n'y a pas assez de mémoire pour placer les composantes fortements connexes dans 'composantes'
 *
 */
template<typename Objet>
void Graphe<Objet>::getComposantesFortementConnexes(
		std::vector<std::vector<Objet> > & composantes) const
{
	Graphe<Objet> f = fermetureGraphe();

	for (Sommet* i = f.listSommets; i != 0; i = i->m_suivant)
	{
		std::vector<Objet> line;
		for (Sommet* j = i; j != 0; j = j->m_suivant)
		{
			if ((f.arcExiste(i->m_numero, j->m_numero)
					&& f._getArc(i, j)->m_cout
							!= std::numeric_limits<int>::max())
					&& (f.arcExiste(j->m_numero, i->m_numero)
							&& f._getArc(j, i)->m_cout
									!= std::numeric_limits<int>::max())
					&& j->m_etat == false)
			{
				j->m_etat = true;
				line.push_back(j->m_etiquette);
			}
		}
		if (!line.empty())
			composantes.push_back(line);
	}
}

/**
 * \brief	Trouve le plus court chemin entre deux points en utilisant l'algorithme de Bellman-Ford et le retourne.
 * \pre	Il y a assez de mémoire pour placer les composantes du chemin 'chemin'
 * \param[in]	eOrigine	l'etiquette du sommet d'origine
 * \param[in]	eDestination	l'etiquette du sommet de destination
 * \param[in]	chemin	Un vector de type etiquette qui contient le chemin du parcours
 *
 * \post	Le cout total est retourné, -1 s'il n'y a pas de chemin
 * \post	Le graphe original reste inchangé
 * \post	La liste des étiquettes des sommets à parcourir est retournée dans le vector 'chemin'
 *
 * \exception	bad_alloc	Il n'y a pas assez de mémoire pour placer le chemin dans 'chemin'
 * \exception	logic_error	Le sommet d'origine ou de destination n'existe pas
 *
 * \return	Le coût du parcours trouvé
 */
template<typename Objet>
int Graphe<Objet>::bellmanFord(const Objet& eOrigine, const Objet& eDestination,
		std::vector<Objet> & chemin)
{
	if (!etiquetteExiste(eOrigine) && !etiquetteExiste(eDestination)
					&& eOrigine == eDestination)
				throw std::logic_error("Sommet inexistant");

	Sommet * depart = _getSommet(getNumeroSommet(eOrigine));
	Sommet * destination = _getSommet(getNumeroSommet(eDestination));

	_initPathFinding(eOrigine,eDestination,depart,destination);


	//unsigned int size = nbSommets;
	int origine = getNumeroSommet(eOrigine);
	std::vector<int> adjacent;
	std::vector<int> sommets = listerSommets();
	std::vector<int> adjacent2(nbSommets + 1);
	std::vector<Sommet *> SommetsAdjacents;
	std::vector<Arc *> arcs;
	int cout = 0;
	//bool negatif = false;
	//int courant = 0;
	_getSommet(origine)->m_cout = 0;

	for(int i = 1 ; i <= nbSommets; i++)
	{
		adjacent = listerSommetsAdjacents(i);

		for(unsigned int j = 1; j <= adjacent.size(); j++)
		{
			bool existe = false;

			for(unsigned int k = 0; k < arcs.size(); k++)
			{
				if(_getArc(_getSommet(i),_getSommet(j)) == arcs[k])
				{
					existe = true;
				}
			}
			if(!existe)
			{
				if(arcExiste(i,j))
					arcs.push_back(_getArc(_getSommet(i),_getSommet(j)));
			}
		}
	}

	for(int k = 0 ; k < nbSommets - 1; k++){
		for(unsigned int i = 0; i < sommets.size(); i++)
		{
			Sommet * v1 = _getSommet(sommets[i]);
			adjacent = listerSommetsAdjacents(v1->m_numero);

			for(unsigned int j = 0; j < adjacent.size(); j++)
			{
				Sommet * v2 = _getSommet(adjacent[i]);
				//Arc * a1 = _getArc(v1,v2);
				//Arc * a2 = _getSommet(adjacent[i]);
				if(v1->m_cout + getCoutArc(v1->m_numero,v2->m_numero) < v2->m_cout)
				{
					v2->m_cout = v1->m_cout + getCoutArc(v1->m_numero,v2->m_numero);
					v2->m_predecesseur = v1;
				}
			}
		}
	}

	for(unsigned int i = 0; i < sommets.size() -1; i++)
	{
		Sommet * v1 = _getSommet(sommets[i]);
		adjacent = listerSommetsAdjacents(v1->m_numero);

		for(unsigned int j = 0; j < adjacent.size(); j++)
		{
			Sommet * v2 = _getSommet(adjacent[i]);
		//	Arc * a1 = _getArc(v1,v2);
			//Arc * a2 = _getSommet(adjacent[i]);
			if(v1->m_cout + getCoutArc(v1->m_numero,v2->m_numero) < v2->m_cout)
			{
				break;
			}
		}
	}
	cout = destination->m_cout;
	std::vector<int> temp;

	_recupererChemin(destination,chemin);

	return 1;
}

/**
 * \brief	Trouve le plus court chemin entre deux points en utilisant l'algorithme de Dijsktra et le retourne.
 * \pre	Il y a assez de mémoire pour placer les composantes du chemin 'chemin'
 * \post	Le temps de transmission total est retourné, -1 s'il n'y a pas de chemin
 * \post	Le graphe original reste inchangé
 * \post	La liste des sommets à parcourir est retournée dans le vector 'chemin'
 *
 * \param[in]	eOrigine	Nom du sommet d'origine
 * \param[in]	eDestination	Nom du sommet de destination
 * \param[in]	chemin	Un vector de type string qui contient le chemin du parcours
 *
 * \return	Le coût du parcours trouvé
 *
 * \exception	bad_alloc	Il n'y a pas assez de mémoire pour placer le chemin dans 'chemin'
 * \exception	logic_error	Le sommet d'origine ou de destination n'existe pas
 */
template<typename Objet>
int Graphe<Objet>::dijkstra(const Objet& eOrigine, const Objet& eDestination,
		std::vector<Objet> & chemin)
{
	if (!etiquetteExiste(eOrigine) && !etiquetteExiste(eDestination)
			&& eOrigine == eDestination)
		throw std::logic_error("Sommet inexistant");

	int origine = getNumeroSommet(eOrigine);

	Sommet * depart = _getSommet(getNumeroSommet(eOrigine));
	Sommet * destination = _getSommet(getNumeroSommet(eDestination));

	_initPathFinding(eOrigine,eDestination,depart,destination);

	unsigned int size = nbSommets;
	std::vector<int> adjacent = listerSommetsAdjacents(origine);
	std::vector<int> F;
	int courant = 0;
	int cout = 0;

	while (F.size() < size)
	{
		int plusPetitCout = std::numeric_limits<int>::max();
		int petit = 0;

		for (int i = 1; i <= nbSommets; i++)
		{
			if (_getSommet(i)->m_cout < plusPetitCout)
			{
				if (!_getSommet(i)->m_etat)
				{
					plusPetitCout = _getSommet(i)->m_cout;
					petit = _getSommet(i)->m_numero;
				}
			}
		}
		courant = _getSommet(petit)->m_numero;
		_getSommet(petit)->m_etat = true;
		F.push_back(courant);
		adjacent = listerSommetsAdjacents(courant);

		for (unsigned int i = 0; i < adjacent.size(); i++)
		{
			Sommet * v1 = _getSommet(courant);
			Sommet * v2 = _getSommet(adjacent[i]);

			if (v1->m_cout + getCoutArc(v1->m_numero, v2->m_numero)
					< v2->m_cout)
			{
				v2->m_cout = v1->m_cout + getCoutArc(v1->m_numero, v2->m_numero);
				v2->m_predecesseur = v1;
			}
		}
	}


	cout = destination->m_cout;

	_recupererChemin(destination,chemin);

	return cout;
}

template<typename Objet>
void Graphe<Objet>::getPointsArticulation(std::vector<Objet> & sommets)
{
	std::vector<std::vector<Objet> > v;
	getComposantesFortementConnexes(v);

	for (Sommet* i = listSommets; i != 0; i = i->m_suivant)
	{
		Graphe<Objet> g(*this);
		std::vector<std::vector<Objet> > t;

		g.enleverSommet(i->m_numero);
		g.getComposantesFortementConnexes(t);

		if (t.size() > v.size())
		{
			sommets.push_back(i->m_etiquette);
		}

		std::cout << g;
	}
}

/**
 * \brief	Initialise les sommets du graphe dans le but d'utiliser des méthodes pour trouver des chemins.
 * \pre	Le sommet d'origine et le sommet de destination existent
 * \param[in]	eOrigine	l'etiquette du sommet d'origine
 * \param[in]	eDestination	l'etiquette du sommet de destination
 * \param[in]	origine	L'adresse du sommet d'origine
 * \param[in]	destination	L'adresse du sommet de destination
 *
 * \post	Le chemin a été correctement initialisé
 * \exception	logic_error	Le sommet d'origine ou de destination n'existe pas
 *
 */
template<typename Objet>
void Graphe<Objet>::_initPathFinding(const Objet& eOrigine, const Objet& eDestination,
			Sommet * & origine, Sommet * & destination)
{
	std::vector<int> nums = listerSommets();

	for(unsigned int i = 0; i < nums.size(); i++)
	{
		_getSommet(nums[i])->m_cout = std::numeric_limits<int>::max();
		_getSommet(nums[i])->m_predecesseur = 0;
	}

	origine->m_cout = 0;
}

/**
 * \brief	Récupère le chemin à partir d'un vector dans les données sont inversées.
 * \post	Le chemin en ordre (non inversé) est retourné
 * \param[in]	destination	L'adresse de destition d'un sommet
 * \param[in]	chemin	Un vector de type Objet qui contient le chemin du parcours
 */
template<typename Objet>
void Graphe<Objet>::_recupererChemin(Sommet *destination, std::vector< Objet > &chemin)
{
		std::vector<Objet> temp;
		while (destination->m_predecesseur != 0)
		{
			temp.push_back(destination->m_etiquette);
			destination = destination->m_predecesseur;
		}
		temp.push_back(destination->m_etiquette);

		for (int i = temp.size()-1 ; i > -1; i--)
		{
			chemin.push_back(temp[i]);
		}
}


//! \brief		Surcharge de l'op�rateur de sortie.
//! \param[in]	p_out		Le flux de sortie.
//! \param[in]	p_graphe		Le graphe � afficher.
//! \return	Le flux de sortie.
//! \pre		l'�tiquette est un objet comparable, l'op�rateur << y est surcharg�
//! \post		Le nombre de sommets du graphe sera affich�
//! \post		Pour chaque sommet, son num�ro, son �tiquette seront affich�s
//! \post		Pour chaque sommet, tous ses liens, le num�ro des voisins, seront affich�s
template<typename Objet>
std::ostream&
operator <<(std::ostream& p_out, const Graphe<Objet>& p_graphe)
{
	p_out << "Le graphe contient " << p_graphe.nbSommets << " sommet(s)";
	p_out << std::endl;
	typename Graphe<Objet>::Sommet* vertex = p_graphe.listSommets;

	while (vertex != NULL)
	{
		p_out << "Sommet no ";
		p_out << vertex->m_numero;
		p_out << vertex->m_etiquette;
		p_out << std::endl;

		//Afficher les arcs.
		typename Graphe<Objet>::Arc* arc = vertex->m_listeDest;
		if (arc != NULL)
		{
			p_out << "Ce sommet a des liens vers le(s) sommet(s) : ";
			while (arc->m_suivDest != NULL)
			{
				p_out << arc->m_dest->m_numero;
				p_out << "(" << arc->m_cout;
				p_out << "), ";
				arc = arc->m_suivDest;
			}
			p_out << arc->m_dest->m_numero;
			p_out << "(" << arc->m_cout << ")";
		}
		p_out << std::endl;
		vertex = vertex->m_suivant;
	}

	return p_out;
}

//� compl�ter par les autres m�thodes demand�es sur le type Graphe
